Networks of interconnected objects (known as nodes) are commonly used in a number of fields; typical examples are distribution networks of commodities (for example, water). The networks are often partitioned into smaller components (known as parts). For example, a large Water Distribution Network (WDN) may be partitioned into parts known as District Metered Areas (DMAs), or simply districts. This facilitates the localization of leakages in the water distribution network by monitoring a balance between an inflow and an outflow of each district, and it allows supplying each district at lower pressure (thereby saving energy for pumping the water and reducing the leakages); particularly, the districts may be designed to include users with a similar difference of their elevation with respect to the elevation of corresponding sources, so as to allow supplying the districts at a pressure that is only slightly higher than a Minimum Service Pressure (MSP) required by their users.
The process of partitioning a (large) network is quite challenging; this is mainly due to the inherent difficulty of the problem to be tackled, the variety of constrains to be satisfied and the complexity of the terms to be optimized.
For this purpose, a three-phase approach may be used; in this case, the partitioning process is divided into separate phases that are more tractable from a computational point of view. Particularly, in a first phase multiple candidate partitions are generated for the network, in a second phase the candidate partitions are configured, and in a third phase the candidate partitions are optimized (and one of them is then selected).
In this context, the most challenging activity is generally that of configuring the candidate partitions. For example, in a water distribution network this involves determining the arrangement of intercepting valves (for closing connections between different parts) and of regulating valves (for regulating the pressure of the water supplied from one part to another part) of each candidate partition.
An example of partitioning process for a water distribution network is described in “Optimal design of district metered areas in water distribution networks, Francesco De Paola, Nicola Fontana, Enzo Galdiero, Maurizio Giugni, GianlucaSorgentidegliUberti and Marcello Vialetti, 12th International Conference on Computing and Control for the Water Industry, CCWI2013” (the entire disclosure of which is herein incorporated by reference).
With reference in particular to the activity of configuring a specific partition, this document points out that in most cases the partition may have districts without sources (inner districts) or districts whose sources are not able to meet a total demand of its users; in order to supply these districts, connections with other districts are opened. For this purpose, a heuristic technique is described wherein all the districts are put into a set and taken into account in succession. If the sources of each (current) district are able to meet its total demand (i.e., it is supplied), the district is removed from the set. On the other hand (i.e., when the total demand of the district is not met, comprising for an inner district), if the district has no adjacent supplied districts it is skipped. Otherwise, the shortest paths to the users of this district from the sources of the adjacent supplied districts (not already connected thereto) are computed according to their hydraulic resistances (based on diameter, length and roughness of the corresponding connections). The connection between the two districts in the minimum shortest path is opened and a corresponding source is added, thereafter the district is removed from the set. The same operations are repeated until the set is emptied.
However, the selection of the adjacent supplied districts for supplying the other districts depends on the order by which such adjacent districts become supplied (which has no physical significance). Moreover, the capacity of the sources is not taken into account (so that there is no guarantee that the connections being opened are the most appropriate ones). In addition, hydraulic simulations may only be performed after completing the configuration of the partition.